# This is free and unencumbered software released into the public domain.
#
# Anyone is free to copy, modify, publish, use, compile, sell, or
# distribute this software, either in source code form or as a compiled
# binary, for any purpose, commercial or non-commercial, and by any
# means.
#
# In jurisdictions that recognize copyright laws, the author or authors
# of this software dedicate any and all copyright interest in the
# software to the public domain. We make this dedication for the benefit
# of the public at large and to the detriment of our heirs and
# successors. We intend this dedication to be an overt act of
# relinquishment in perpetuity of all present and future rights to this
# software under copyright law.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
# OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
# ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
# OTHER DEALINGS IN THE SOFTWARE.
#
# For more information, please refer to <http://unlicense.org/>

from collections import namedtuple
import sys
import re
from typing import Sequence, Set, Tuple
# from collections import namedtuple
from typing import List, NamedTuple, Union
from thefuzz import fuzz

# These define the structure of the history, and correspond to diff output with
# lines that start with a space, a + and a - respectively.
class Keep(NamedTuple):
    line: str


class Insert(NamedTuple):
    line: str


class Remove(NamedTuple):
    line: str


# See frontier in myers_diff
class Frontier(NamedTuple):
    x: int
    history: List[Union[Keep, Insert, Remove]]


punctuation_symbols = [
    ";",
    ",",
    ":",
    ".",
    "(",
    ")",
    "{",
    "}",
    "[",
    "]",
    "'",
    '"',
    "`",
    "+",
    "-",
    "*",
    "/",
    "=",
    "==",
    "!=",
    "!==",
    ">",
    "<",
    ">=",
    "<=",
    "&&",
    "||",
    "!",
    "&",
    "|",
    "^",
    "~",
    "<<",
    ">>",
    "?:",
]
rust_keywords = [
    "as",
    "async",
    "await",
    "break",
    "const",
    "continue",
    "crate",
    "dyn",
    "else",
    "enum",
    "extern",
    "false",
    "fn",
    "for",
    "if",
    "impl",
    "in",
    "let",
    "loop",
    "match",
    "mod",
    "move",
    "mut",
    "pub",
    "ref",
    "return",
    "Self",
    "self",
    "static",
    "struct",
    "super",
    "trait",
    "true",
    "type",
    "unsafe",
    "use",
    "where",
    "while",
]


def remove_comments(line: str) -> str:
    # Remove single line comments
    line = re.sub(r"//.*", "", line)
    # Remove multi-line comments
    line = re.sub(r"/\*.*?\*/", "", line, flags=re.DOTALL)
    return line


def code_line_to_words(line: str) -> List[str]:
    # 去除注释
    # line = remove_comments(line)
    # 去除操作符
    for symbol in punctuation_symbols:
        line = line.replace(symbol, " ")

    # 替换连续空格
    line = re.sub(r"\s+", " ", line)
    # Split the line into words
    words = line.split()
    # Remove Rust keywords while preserving order
    words = [word for word in words if word not in rust_keywords]
    # Remove duplicates while preserving order
    seen = set()
    words_no_duplicates = [x for x in words if not (x in seen or seen.add(x))]
    return words_no_duplicates


def _word_equal(lhs: str, rhs: str, threshold: int = 90) -> bool:
    lhs = lhs.lower().replace("_", "")
    rhs = rhs.lower().replace("_", "")
    return fuzz.ratio(lhs, rhs) > threshold

def jaccard_similarity(list1: List[str], list2: List[str], threshold: int = 70) -> float:
    set1 = set(list1)
    set2 = set(list2)

    intersection = []
    
    for set1_item in set1:
        for set2_item in set2:
            if _word_equal(set1_item, set2_item, threshold):
                if not any([_word_equal(set1_item, i, threshold) for i in intersection]):
                    intersection.append(set1_item)
    # 计算并集
    union = []
    for set1_item in set1:
        if not any([_word_equal(set1_item, i, threshold) for i in intersection]):
            union.append(set1_item)
    for set2_item in set2:
        if not any([_word_equal(set2_item, i, threshold) for i in intersection]):
            union.append(set2_item)
    union.extend(intersection)

    # 计算Jaccard相似度
    if len(union) == 0:
        return 0.0  # 如果并集为空，返回0.0，避免除以0的错误
    else:
        return float(len(intersection)) / len(union)

def code_line_similarity(lhs_line: str, rhs_line: str) -> float:
    if lhs_line.strip() == rhs_line.strip():
        return True
    lhs_words = code_line_to_words(lhs_line)
    rhs_words = code_line_to_words(rhs_line)
    return jaccard_similarity(lhs_words, rhs_words)

def code_line_equal(lhs_line: str, rhs_line: str, threshold: float = 0.4) -> bool:
    if lhs_line.strip() == rhs_line.strip():
        return True
    lhs_words = code_line_to_words(lhs_line)
    rhs_words = code_line_to_words(rhs_line)
    # if jaccard_similarity(lhs_words, rhs_words) > 0.1:
    #     print(lhs_words)
    #     print(rhs_words)
    #     print(jaccard_similarity(lhs_words, rhs_words))
    #     print("====")
    return jaccard_similarity(lhs_words, rhs_words) > threshold


def diff_to_string(diff_result: List[Union[Keep, Insert, Remove]], line_number: bool = True) -> str:
    """将差异结果转换为字符串

    Args:
        diff_result (List[Union[Keep, Insert, Remove]]): 差异结果
        line_number (bool, optional): 是否显示行号. Defaults to True.

    Returns:
        str: 字符串表示的差异
    """
    ret = ""
    before_i = 1
    after_i = 1
    for elem in diff_result:
        if isinstance(elem, Keep):
            if line_number:
                ret += "{i: <4}  {line}\n".format(i=before_i, line=elem.line)
            else:
                ret += f"  {elem.line}\n"
            before_i += 1
            after_i += 1
        elif isinstance(elem, Insert):
            if line_number:
                ret += "{i: <4} + {line}\n".format(i=after_i, line=elem.line)
            else:
                ret += f"+ {elem.line}\n"
            after_i += 1
        elif isinstance(elem, Remove):
            if line_number:
                ret += "{i: <4} - {line}\n".format(i=before_i, line=elem.line)
            else:
                ret += f"- {elem.line}\n"
            before_i += 1
        else:
            raise ValueError("Unknown diff element type")

    return ret


def fuzz_myers_diff(a_lines: Sequence[str], b_lines: Sequence[str]) -> List[Union[Keep, Insert, Remove]]:
    """
    An implementation of the Myers diff algorithm.
    See http://www.xmailserver.org/diff2.pdf
    """
    # This marks the farthest-right point along each diagonal in the edit
    # graph, along with the history that got it there
    frontier = {1: Frontier(0, [])}

    def one(idx):
        """
        The algorithm Myers presents is 1-indexed; since Python isn't, we
        need a conversion.
        """
        return idx - 1

    a_max = len(a_lines)
    b_max = len(b_lines)
    for d in range(0, a_max + b_max + 1):
        for k in range(-d, d + 1, 2):
            # This determines whether our next search point will be going down
            # in the edit graph, or to the right.
            #
            # The intuition for this is that we should go down if we're on the
            # left edge (k == -d) to make sure that the left edge is fully
            # explored.
            #
            # If we aren't on the top (k != d), then only go down if going down
            # would take us to territory that hasn't sufficiently been explored
            # yet.
            go_down = k == -d or (k != d and frontier[k - 1].x < frontier[k + 1].x)

            # Figure out the starting point of this iteration. The diagonal
            # offsets come from the geometry of the edit grid - if you're going
            # down, your diagonal is lower, and if you're going right, your
            # diagonal is higher.
            if go_down:
                old_x, history = frontier[k + 1]
                x = old_x
            else:
                old_x, history = frontier[k - 1]
                x = old_x + 1

            # We want to avoid modifying the old history, since some other step
            # may decide to use it.
            history = history[:]
            y = x - k

            # We start at the invalid point (0, 0) - we should only start building
            # up history when we move off of it.
            if 1 <= y <= b_max and go_down:
                history.append(Insert(b_lines[one(y)]))
            elif 1 <= x <= a_max:
                history.append(Remove(a_lines[one(x)]))

            # Chew up as many diagonal moves as we can - these correspond to common lines,
            # and they're considered "free" by the algorithm because we want to maximize
            # the number of these in the output.
            while x < a_max and y < b_max and code_line_equal(a_lines[one(x + 1)], b_lines[one(y + 1)]):
            # while x < a_max and y < b_max and a_lines[one(x + 1)] == b_lines[one(y + 1)]:
                x += 1
                y += 1
                history.append(Keep(a_lines[one(x)]))

            if x >= a_max and y >= b_max:
                # If we're here, then we've traversed through the bottom-left corner,
                # and are done.
                return history
            else:
                frontier[k] = Frontier(x, history)

    assert False, "Could not find edit script"


if __name__ == "__main__":
    lhs = """
// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:3
fn swap(left: &mut i32, right: &mut i32) {
    let temp = *left;
    *left = *right;
    *right = temp;
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:3

// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:10
fn bubble_sort(arry: &mut [i32], length: usize) {
    for i in 0..length-1 {
        for j in 0..length-i-1 {
            if arry[j] > arry[j+1] { // changed to use '>' for bubble sort
                let (left, right) = arry.split_at_mut(j + 1); // split the array into two parts
                swap(&mut left[j], &mut right[0]); // swap the elements
            }
        }
    }
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:10

// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:25
fn main() {
    let mut input_array = [12, 43, 9, 13, 67, 98, 101, 89, 3, 35];
    println!("bubble sort the array");

    bubble_sort(&mut input_array, 10);

    // print the array
    print_array(&input_array, 10);
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:25
"""
    rhs = """
// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:3
fn swap(left: &mut i32, right: &mut i32) {
    let temp = *left;
    *left = *right;
    *right = temp;
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:3

// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:10
fn bubble_sort(arry: &mut [i32], length: usize) {
    for i in 0..length-1 {
        for j in 0..length-i-1 {
            if arry[j] > arry[j+1] { // changed to use '>' for bubble sort
                let (left, right) = arry.split_at_mut(j + 1); // split the array into two parts
                swap(&mut left[j], &mut right[0]); // swap the elements
            }
        }
    }
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:10

// CHERNC_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:25
fn main() {
    let mut input_array = [12, 43, 9, 13, 67, 98, 101, 89, 3, 35];
    println!("bubble sort the array");

    bubble_sort(&mut input_array, 10);

    // print the array
    print_array(&input_array, 10);
}
// CHERNC_END_MARK: /data/wangjun/github/Chern-C/examples/bubblesort/bubblesort.c:25
"""

    a_lines = [line.rstrip() for line in lhs.splitlines()]

    b_lines = [line.rstrip() for line in rhs.splitlines()]

    diff = fuzz_myers_diff(a_lines, b_lines)
    for elem in diff:
        if isinstance(elem, Keep):
            print(" " + elem.line)
        elif isinstance(elem, Insert):
            print("+" + elem.line)
        else:
            print("-" + elem.line)
